
class Solution {
    //解法一
    public String longestCommonPrefix1(String[] strs) {
        if (strs == null) return null;
        if (strs.length == 1) return strs[0];
        StringBuilder ret = new StringBuilder();
        int i = 0;
        while (true) {
            if (strs[0].length() <= i) {
                break;
            }
            char ch = strs[0].charAt(i);

            int flag = 0;

            for (int j = 1; j < strs.length; j++) {
                if (strs[j].length() <= i || strs[j].charAt(i) != ch) {
                    flag = 1;
                    break;
                }
            }

            if (flag == 1) break;

            ret.append(ch);
            i++;
        }
        return ret.toString();
    }

    //解法二
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) return strs[0];
        String ret = strs[0];
        for (String str : strs) {
            ret = chack(ret, str);
        }
        return ret;
    }

    private String chack(String str1, String str2) {
        int i = 0;
        StringBuilder ret = new StringBuilder();
        while (str1.length() > i && str2.length() > i && str1.charAt(i) == str2.charAt(i)) {
            ret.append(str1.charAt(i));
            i++;
        }
        return ret.toString();
    }

    //最长回文子串
    public String longestPalindrome(String s) {
        String ret = "";
        for (int i = 0; i < s.length(); i++) {
            //回文串长度为奇数
            int left = i, right = i;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            left++;
            right--;
            if (right - left + 1 > ret.length()) {
                ret = s.substring(left, right + 1);
            }
            //回文串长度为偶数
            left = i;
            right = i + 1;
            if (right >= s.length() || s.charAt(left) != s.charAt(right)) continue;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            left++;
            right--;
            if (right - left + 1 > ret.length()) {
                ret = s.substring(left, right + 1);
            }
        }
        return ret;
    }
    //11
    //1

    //二进制求和
    public String addBinary(String a, String b) {
        int m = Math.max(a.length(), b.length());
        StringBuilder ret = new StringBuilder();
        char[] str1 = reverse(a.toCharArray());
        char[] str2 = reverse(b.toCharArray());
        int k = 0;//进位
        for (int i = 0; i < m; i++) {
            int x = i < str1.length ? str1[i] - '0' : 0;
            int y = i < str2.length ? str2[i] - '0' : 0;
            int n = x + y + k;
            k = n / 2;
            n %= 2;
            char ch = (char) (n + '0');
            ret.append(ch);
        }
        while (k > 0) {
            ret.append('1');
            k--;
        }
        char[] str = reverse(ret.toString().toCharArray());
        return new String(str);
    }

    private char[] reverse(char[] str) {
        for (int i = 0, j = str.length - 1; i < j; i++, j--) {
            char ch = str[i];
            str[i] = str[j];
            str[j] = ch;
        }
        return str;
    }


    //高精度乘法
    public String multiply1(String num1, String num2) {
        //1.准备工作
        int m = num1.length(), n = num2.length();
        char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();
        int[] tmp = new int[m + n - 1];

        //2.无进位相乘,然后相加
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
            }
        }

        //3.处理进位
        int cur = 0, t = 0;
        StringBuffer ret = new StringBuffer();
        while (cur < m + n - 1 || t != 0) {
            if (cur < m + n - 1) t += tmp[cur++];
            ret.append((char)((char)(t%10)+'0'));
            t/=10;
        }

        //4.处理前导0
        while(ret.length()>1 && ret.charAt(ret.length()-1)=='0') {
            ret.deleteCharAt(ret.length()-1);
        }

        return ret.reverse().toString();
    }
}

public class Test {
    public static void main(String[] args) {
        String ret = new Solution().addBinary("1010", "1011");
        System.out.println(ret);
    }

    public static void main1(String[] args) {
        //String[] strs = {""};
        String ret = new Solution().longestPalindrome("a");
        System.out.println(ret);
    }
}
